package org.example.ch13;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class FindWords2 {
    class TrieNode{
        String s;
        TrieNode[] tns = new TrieNode[26];
    }

    Set<String> set = new HashSet<>();
    char[][] board;
    int n,m;
    TrieNode root = new TrieNode();
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    boolean[][] vis = new boolean[15][15];


    void insert (String s){
        TrieNode p = root;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if(p.tns[u] == null){
                p.tns[u] = new TrieNode();
            }
            p = p.tns[u];
        }
        p.s =s;
    }

    public List<String> findWords(char[][] _board,String[] words){
        //初始化棋盘
        board = _board;
        //初始化棋盘的长和宽
         m = board.length;
         n = board[0].length;
        for(String s:words){
            insert(s);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {

                int index = board[i][j] - 'a';
                if(root.tns[index] != null){
                    vis[i][j] = true;
                    //回溯算法进行查找
                    dfs(i,j,root.tns[index]);
                    vis[i][j] = false;
                }
            }
        }
        List<String> ans = new ArrayList<>();
        for (String s : set) {
            ans.add(s);
        }
        return ans;
    }

    /**
     * 深度优先遍历
     * @param i
     * @param j
     * @param trieNode
     */
    public void dfs(int i,int j,TrieNode trieNode){
        //递归的终止条件
        if(trieNode.s != null){
            set.add(trieNode.s);
            return;
        }
        //向4个方向深度遍历
        for (int[] d:dirs) {
            int dx = i+d[0];
            int dy = j+d[1];
            if(dx<0 || dx>=m || dy<0 || dy>=n){
                continue;
            }
            if(vis[dx][dy]){
                continue;
            }

            int index = board[dx][dy] - 'a';
            if(trieNode.tns[index] != null){
                vis[dx][dy] = true;
                //下探到下一层递归，传入主角
                dfs(dx,dy,trieNode.tns[index]);
                vis[dx][dy] = false;
            }
        }

    }

    public static void main(String[] args) {
        FindWords2 find = new FindWords2();
        char[][] board = new char[][]{
                {'o','a','a','n'},
                {'e','t','a','e'},
                {'i','h','k','r'},
                {'i','f','l','v'}};
        String[] words = new String[]{"oath","pea","eat","rain"};


        List<String> list = find.findWords(board,words);
        for (String str:list){
            System.out.println("匹配的字符串："+str);
        }
    }
}
